The present invention relates to a cache system adopting an LRU (Least Recently Used) system in a replacement algorithm for cache blocks, and to a magnetic disk controller incorporating the cache system.
Disk cache systems capable of high-speed data access to magnetic disks have been developed. A disk cache is a memory device using a semiconductor RAM and is designed to eliminate an access gap between a high-speed main memory and low-speed large-capacity secondary memories (i.e., magnetic disk units). The disk cache is normally arranged between the main memory and a magnetic disk unit, in a magnetic disk controller, and serves as a data buffer.
The principle of the disk cache is the same as that of a central processing unit (CPU) cache. If a CPU first accesses part of a file, necessary data blocks are stored on a disk. In this case, the disk cache does not contribute to such CPU access.
Necessary blocks are transferred from the disk to the main memory. At the same time, they are written in the disk cache. If the CPU subsequently accesses the same blocks, they are transferred from the disk cache, but not from the disk. The access time of the magnetic disk unit is normally 20 to 30 ms, while the access time of the disk cache is about 1 to 3 ms. The access time can, therefore, be decreased to about 1/10. When a total access time is regarded as an input/output response time including data transfer time and channel wait time, it can be normally decreased to 1/2 to 1/3.
Since a disk cache capacity is smaller (about 1/1000) than that of the disk, all file blocks required by the CPU are not always stored in the disk cache. In order to load new blocks when the disk cache is filled with file blocks, old blocks must be removed from it. When accessing of the cache allows retrieval of necessary data from the cache, it is called a "hit", and when retrieval of necessary data cannot be performed, it is called a "miss". The average hit times per times or the difference of the cache is called a hit ratio.
In addition to the disk cache, disk cache mechanism components are a disk cache handler as a program in the input/output controller, a data transfer mechanism between the main memory and the disk cache, and a disk cache directory. The disk cache handler cooperates with an operating system (OS) to determine the hit/miss ratio of the disk cache, control of data transfer between the main memory, the disk cache, and the magnetic disks, and acquisition of data representing utilization efficiency of the disk cache and the hit ratio, and so on.
Write access schemes include a write through scheme and a write back scheme. The write through scheme is called a store through scheme for writing directory data in a disk. The cache hit processing is performed in such a way that the cache hit block is disabled by not writing data therein, or the data is written in the cache hit block after it is directly written into the disk.
The write back scheme is called a store in, copy back, or post store scheme. According to this scheme, the disk cache write is the highest priority. When a data write into a file in the disk cache is completed, data input/output is completed. If the file is unnecessary or the cache block storing the file must be emptied for other files, data is transferred from the cache to the disk.
In the disk cache, data copying from the magnetic disk to the cache memory is called staging, and copying from the cache memory to the magnetic disk is called destaging.
A typical disk cache memory mapping scheme is a set associative scheme. According to this scheme, the magnetic disk and the disk cache memory are divided into a plurality of blocks (e.g., one block=one track=64 sectors). Blocks belong to columns, respectively. In order to transfer a given block from the magnetic disk to the cache memory, this block is written in an identical column of the cache memory and data (representing which block, i.e., a block number, in the magnetic disk is stored in the cache memory) is stored in the directory in units of columns. By referring this directory, it is possible to determine whether specific data is stored in the cache memory or not. If the data is stored in the cache memory, it can be read out, not from the magnetic disk unit but from the cache memory.
The disk cache replacement algorithm is an LRU algorithm. LRU stands for "Least Recently Used." According to the LRU algorithm, the block which stays in the cache for the longest period after the last access is selected as the least necessary block. In a disk cache having no empty space, if the cache memory must be assigned for new staging, the least necessary track data is removed to obtain an empty space. The LRU algorithm is used to assure this empty space.
If a cache hit occurs as a result of the directory search, the LRU value in the cache directory corresponding to the hit cache block is initialized to "0". In the case of cache miss, the LRU value corresponding to the cache block to be replaced must be registered again. In this case, if the cache miss occurs in the read request mode, the corresponding data block is read out from the magnetic disk unit and is stored in the cache block in the cache memory which is to be replaced.
In a conventional cache system, LRU setting values are determined regardless of the data blocks stored in the cache memory.
The frequency of use of the data blocks stored in the cache blocks varies according to different types of files. Once a data block having a low frequency of use is stored in the cache block, the resident possibility of that data block in the cache memory is often higher than that of a file having a high frequency of use. Because of this, a decrease in hit rate of the cache memory tends to occur.
In the conventional disk cache system of this type, disk write operation is always performed in response to a disk write instruction from a host system. According to the conventional system, even if the data in the disk area subjected to disk write is stored in the cache memory (even if cache hit occurs), the contents of the cache memory and the disk unit are simultaneously updated. This is to not allow non-updated data to be left in the disk when a failure, such as a power failure, occurs.
According to the system described above, however, high performance of the disk cache structure can be achieved only when the read frequency is high. If the write frequency is high, a great deal of improvement in performance cannot be expected.
When a power unit free from the effects of power failure is used, disk write need not be performed at the time of cache hit in the write request mode. However, a power unit of this type is very expensive.
Assume that a read access request for a given file is sent from the CPU. The magnetic disk controller retrieves a disk cache directory (a table having file information such as a file name, a file size, and a file address) and checks if the data block of interest is stored in the disk cache. If cache hit occurs, the corresponding data block is transferred from the cache memory to the main memory.
In the case of cache miss, however, several blocks (usually those for one track) including the required block are sent to the cache memory, and only the required block is sent to the main memory. Data transfer to the cache memory is performed simultaneously with that to the main memory. However, the blocks can be transferred to the cache memory and the block of interest can be transferred to the main memory thereafter.
A large demand has arisen for a magnetic disk controller for satisfying the above-mentioned two transfer schemes and for performing effective data transfer control if a cache miss occurs.
If a cache memory is used in common by 4 magnetic disk drives, e.g., DK0 through DK3, different cache memory areas are permanently assigned for respective drives DK0 through DK3, and a directory memory having a corresponding memory allocation is prepared, as shown in FIG. 1.
According to the system described above, however, the limited area of the cache memory is divided, and the cache locations respectively assigned to the magnetic disk drives are decreased, leading to a reduction in the cache hit rate. If the access frequency varies for the different drives, the frequency of use of the cache memory location corresponding to the drive having the lowest access frequency is decreased. As a result, the overall utilization efficiency of the cache memory is degraded.